{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find the String with LCP"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #union-find #array #string #dynamic-programming #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #并查集 #数组 #字符串 #动态规划 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findTheString"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #找出对应 LCP 矩阵的字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>对任一由 <code>n</code> 个小写英文字母组成的字符串 <code>word</code> ，我们可以定义一个 <code>n x n</code> 的矩阵，并满足：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>lcp[i][j]</code> 等于子字符串&nbsp;<code>word[i,...,n-1]</code> 和 <code>word[j,...,n-1]</code> 之间的最长公共前缀的长度。</li>\n",
    "</ul>\n",
    "\n",
    "<p>给你一个 <code>n x n</code> 的矩阵 <code>lcp</code> 。返回与 <code>lcp</code> 对应的、按字典序最小的字符串&nbsp;<code>word</code> 。如果不存在这样的字符串，则返回空字符串。</p>\n",
    "\n",
    "<p>对于长度相同的两个字符串 <code>a</code> 和 <code>b</code> ，如果在 <code>a</code> 和 <code>b</code> 不同的第一个位置，字符串 <code>a</code> 的字母在字母表中出现的顺序先于 <code>b</code> 中的对应字母，则认为字符串 <code>a</code> 按字典序比字符串 <code>b</code> 小。例如，<code>\"aabd\"</code> 在字典上小于 <code>\"aaca\"</code> ，因为二者不同的第一位置是第三个字母，而&nbsp;<code>'b'</code> 先于 <code>'c'</code> 出现。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>lcp = [[4,0,2,0],[0,3,0,1],[2,0,2,0],[0,1,0,1]]\n",
    "<strong>输出：</strong>\"abab\"\n",
    "<strong>解释：</strong>lcp 对应由两个交替字母组成的任意 4 字母字符串，字典序最小的是 \"abab\" 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>lcp = [[4,3,2,1],[3,3,2,1],[2,2,2,1],[1,1,1,1]]\n",
    "<strong>输出：</strong>\"aaaa\"\n",
    "<strong>解释：</strong>lcp 对应只有一个不同字母的任意 4 字母字符串，字典序最小的是 \"aaaa\" 。 \n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>lcp = [[4,3,2,1],[3,3,2,1],[2,2,2,1],[1,1,1,3]]\n",
    "<strong>输出：</strong>\"\"\n",
    "<strong>解释：</strong>lcp[3][3] 无法等于 3 ，因为 word[3,...,3] 仅由单个字母组成；因此，不存在答案。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n ==&nbsp;</code><code>lcp.length == </code><code>lcp[i].length</code>&nbsp;<code>&lt;= 1000</code></li>\n",
    "\t<li><code><font face=\"monospace\">0 &lt;= lcp[i][j] &lt;= n</font></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-the-string-with-lcp](https://leetcode.cn/problems/find-the-string-with-lcp/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-the-string-with-lcp](https://leetcode.cn/problems/find-the-string-with-lcp/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[4,0,2,0],[0,3,0,1],[2,0,2,0],[0,1,0,1]]', '[[4,3,2,1],[3,3,2,1],[2,2,2,1],[1,1,1,1]]', '[[4,3,2,1],[3,3,2,1],[2,2,2,1],[1,1,1,3]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheString(self, lcp: List[List[int]]) -> str:\n",
    "        i, n = 0, len(lcp)\n",
    "        s = [''] * n\n",
    "        for c in ascii_lowercase:\n",
    "            while i < n and s[i]: i += 1\n",
    "            if i == n: break  # 构造完毕\n",
    "            for j in range(i, n):\n",
    "                if lcp[i][j]:\n",
    "                    s[j] = c\n",
    "        if '' in s: return \"\"  # 没有构造完\n",
    "\n",
    "        # 直接在原数组上验证\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                actual_lcp = 0 if s[i] != s[j] else 1 if i == n - 1 or j == n - 1 else lcp[i + 1][j + 1] + 1\n",
    "                if lcp[i][j] != actual_lcp: return \"\"\n",
    "        return \"\".join(s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheString(self, lcp: List[List[int]]) -> str:\n",
    "        i, n = 0, len(lcp)\n",
    "        s = [''] * n\n",
    "        for c in ascii_lowercase:\n",
    "            while i < n and s[i]: i += 1\n",
    "            if i == n: break  # 构造完毕\n",
    "            for j in range(i, n):\n",
    "                if lcp[i][j]:\n",
    "                    s[j] = c\n",
    "        if '' in s: return \"\"  # 没有构造完\n",
    "\n",
    "        # 直接在原数组上验证\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                actual_lcp = 0 if s[i] != s[j] else 1 if i == n - 1 or j == n - 1 else lcp[i + 1][j + 1] + 1\n",
    "                if lcp[i][j] != actual_lcp: return \"\"\n",
    "        return \"\".join(s)\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheString(self, lcp: List[List[int]]) -> str:\n",
    "        i, n = 0, len(lcp)\n",
    "        s = [''] * n\n",
    "        for c in ascii_lowercase:\n",
    "            while i < n and s[i]: i += 1\n",
    "            if i == n: break  # 构造完毕\n",
    "            for j in range(i, n):\n",
    "                if lcp[i][j]:\n",
    "                    s[j] = c\n",
    "        if '' in s: return \"\"  # 没有构造完\n",
    "\n",
    "        # 直接在原数组上验证\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                actual_lcp = 0 if s[i] != s[j] else 1 if i == n - 1 or j == n - 1 else lcp[i + 1][j + 1] + 1\n",
    "                if lcp[i][j] != actual_lcp: return \"\"\n",
    "        return \"\".join(s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from string import ascii_lowercase as al\n",
    "class Solution:\n",
    "    def findTheString(self, lcp: List[List[int]]) -> str:\n",
    "        ls = len(lcp)\n",
    "        # 合规性检测\n",
    "        for i in range(ls):\n",
    "            if lcp[i][i] != ls - i:\n",
    "                return ''\n",
    "            for j in range(i, ls):\n",
    "                if lcp[i][j] != lcp[j][i] or lcp[i][j] + j > ls:\n",
    "                    return ''\n",
    "\n",
    "        s = [set(al) if i else 'a' for i in range(ls)]\n",
    "        # rule = r[i] = [j, k]\n",
    "        # s[i]必须与s[j]和s[k]一致\n",
    "        r = [set() for _ in range(ls)]\n",
    "\n",
    "        # 当前循环确定字符s[j]\n",
    "        for j in range(1, ls):\n",
    "            # 之前已经确定过字符s[j]了\n",
    "            if type(s[j]) == str:\n",
    "                continue\n",
    "            memo = s[j]\n",
    "            for i in range(j):\n",
    "                n = lcp[i][j]\n",
    "                # s[j]与s[i]的前n个字符一致\n",
    "                if n:\n",
    "                    # i < j，所以s[:j]已经在之前的循环中确定了\n",
    "                    for k in range(n):\n",
    "                        if s[i+k] not in s[j+k]:\n",
    "                            return ''\n",
    "                        s[j+k] = s[i+k]\n",
    "                # s[j] != s[i]\n",
    "                else:\n",
    "                    if s[i] in s[j]:\n",
    "                        memo.remove(s[i])\n",
    "            if not memo:\n",
    "                return ''\n",
    "            s[j] = min(memo)\n",
    "        \n",
    "        # 在确定了所有字符之后，重新检测一遍lcp表是否有误\n",
    "        for i in range(ls):\n",
    "            for j in range(i+1, ls):\n",
    "                n = lcp[i][j]\n",
    "                if s[i:i+n] != s[j:j+n]:\n",
    "                    return ''\n",
    "                if lcp[i][j] + j < ls and s[i:i+n+1] == s[j:j+n+1]:\n",
    "                    return ''\n",
    "\n",
    "        return ''.join(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheString(self, lcp: List[List[int]]) -> str:\n",
    "        i, n = 0, len(lcp)\n",
    "        s = [''] * n\n",
    "        for c in ascii_lowercase:\n",
    "            while i < n and s[i]: i += 1\n",
    "            if i == n: break  # 构造完毕\n",
    "            for j in range(i, n):\n",
    "                if lcp[i][j]:\n",
    "                    s[j] = c\n",
    "        if '' in s: return \"\"  # 没有构造完\n",
    "\n",
    "        # 直接在原数组上验证\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                actual_lcp = 0 if s[i] != s[j] else 1 if i == n - 1 or j == n - 1 else lcp[i + 1][j + 1] + 1\n",
    "                if lcp[i][j] != actual_lcp: return \"\"\n",
    "        return \"\".join(s)\n",
    "\n",
    "# 作者：灵茶山艾府\n",
    "# 链接：https://leetcode.cn/problems/find-the-string-with-lcp/solutions/2120175/tan-xin-gou-zao-yan-zheng-o1e-wai-kong-j-82ik/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheString(self, lcp: List[List[int]]) -> str:\n",
    "        i, n = 0, len(lcp)\n",
    "        s = [''] * n\n",
    "        for c in ascii_lowercase:\n",
    "            while i < n and s[i]: i += 1\n",
    "            if i == n: break  # 构造完毕\n",
    "            for j in range(i, n):\n",
    "                if lcp[i][j]:\n",
    "                    s[j] = c\n",
    "        if '' in s: return \"\"  # 没有构造完\n",
    "\n",
    "        # 直接在原数组上验证\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                actual_lcp = 0 if s[i] != s[j] else 1 if i == n - 1 or j == n - 1 else lcp[i + 1][j + 1] + 1\n",
    "                if lcp[i][j] != actual_lcp: return \"\"\n",
    "        return \"\".join(s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheString(self, lcp: List[List[int]]) -> str:\n",
    "        i, n = 0, len(lcp)\n",
    "        s = [''] * n\n",
    "        for c in ascii_lowercase:\n",
    "            while i < n and s[i]: i += 1\n",
    "            if i == n: break  # 构造完毕\n",
    "            for j in range(i, n):\n",
    "                if lcp[i][j]:\n",
    "                    s[j] = c\n",
    "        if '' in s: return \"\"  # 没有构造完\n",
    "\n",
    "        # 直接在原数组上验证\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                actual_lcp = 0 if s[i] != s[j] else 1 if i == n - 1 or j == n - 1 else lcp[i + 1][j + 1] + 1\n",
    "                if lcp[i][j] != actual_lcp: return \"\"\n",
    "        return \"\".join(s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheString(self, lcp: List[List[int]]) -> str:\n",
    "        i, n = 0, len(lcp)\n",
    "        s = [''] * n\n",
    "        for c in ascii_lowercase:\n",
    "            while i < n and s[i]:\n",
    "                i += 1\n",
    "            if i == n:\n",
    "                break\n",
    "            for j in range(i, n):\n",
    "                if lcp[i][j]:\n",
    "                    s[j] = c\n",
    "        if '' in s:\n",
    "            return \"\"\n",
    "        \n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                actual_lcp = 0 if s[i] != s[j] else 1 if i == n - 1 or j == n - 1 else lcp[i + 1][j + 1] + 1\n",
    "                if lcp[i][j] != actual_lcp:\n",
    "                    return \"\"\n",
    "        return \"\".join(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from string import ascii_lowercase\n",
    "class Solution:\n",
    "    def findTheString(self, lcp: List[List[int]]) -> str:\n",
    "        i,n=0,len(lcp)\n",
    "        s=['']*n\n",
    "        for c in ascii_lowercase:\n",
    "            while i<n and s[i]:i+=1\n",
    "            if i==n:break #构造完毕\n",
    "            for j in range(i,n):\n",
    "                if lcp[i][j]:s[j]=c \n",
    "        if '' in s:return ''#没有构造完\n",
    "        #直接在原数组上验证\n",
    "        for i in range(n-1,-1,-1):\n",
    "            for j in range(n-1,-1,-1):\n",
    "                # # actual_lcp=0 if s[i]!=s[j] else 1 if \n",
    "                # if i==n-1 or j==n-1:\n",
    "                #     if s[i]!=s[j]:actual_lcp=0\n",
    "                #     else:actual_lcp=1\n",
    "                # else:\n",
    "                #     actual_lcp=lcp[i+1][j+1]+1\n",
    "                actual_lcp = 0 if s[i] != s[j] else 1 if i == n - 1 or j == n - 1 else lcp[i + 1][j + 1] + 1\n",
    " \n",
    "                if lcp[i][j]!=actual_lcp:return \"\"\n",
    "        return \"\".join(s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheString(self, lcp: List[List[int]]) -> str:\n",
    "        n = len(lcp)\n",
    "        ma = [[0] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            ma[i][i] = 1\n",
    "\n",
    "        for i in range(n):\n",
    "            if lcp[i][i] == 0:\n",
    "                return ''\n",
    "            for j in range(i,n):\n",
    "                if lcp[i][j] != lcp[j][i] or lcp[i][j] > n-j:\n",
    "                    return ''\n",
    "                if (i < n-1 and j < n-1 and lcp[i][j]) and lcp[i][j] != lcp[i+1][j+1]+1:\n",
    "                    return ''\n",
    "                if lcp[i][j]:\n",
    "                    ma[i][j] = 1\n",
    "                    ma[j][i] = 1\n",
    "\n",
    "\n",
    "        table = [0] * n\n",
    "        c = 'a' \n",
    "        for i in range(n):\n",
    "            if table[i] == 0:\n",
    "                if ord(c) > ord('z'):\n",
    "                    return ''\n",
    "                for j in range(n):\n",
    "                    if ma[i][j]:\n",
    "                        if not table[j]:\n",
    "                            table[j] = c\n",
    "                        else:\n",
    "                            return \"\" \n",
    "                c = chr(ord(c) + 1)\n",
    "\n",
    "        return ''.join(table)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheString(self, lcp: List[List[int]]) -> str:\n",
    "        n=len(lcp)\n",
    "        id=0\n",
    "        ans=\"a\"\n",
    "        for j in range(1,n):\n",
    "            for i in range(len(ans)):\n",
    "                if lcp[i][j]>0:\n",
    "                    ans+=ans[i]\n",
    "                    break\n",
    "            if len(ans)<(j+1):\n",
    "                id+=1\n",
    "                if id >=26:\n",
    "                    return \"\"\n",
    "                ans+=chr(ord(\"a\")+id)\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                temp=lcp[i][j]\n",
    "                if temp>min(n-i,n-j) or ans[i:i+temp]!=ans[j:j+temp] or (temp<min(n-i,n-j) and ans[i:i+temp+1]==ans[j:j+temp+1]):\n",
    "                    return \"\"\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheString(self, lcp: List[List[int]]) -> str:\n",
    "        n = len(lcp)\n",
    "        s = ['']*n\n",
    "        i = 0\n",
    "        for c in ascii_lowercase:\n",
    "            while i<n and s[i]:\n",
    "                i+=1\n",
    "            if i == n:\n",
    "                break\n",
    "            for j in range(i,n):\n",
    "                if lcp[i][j]:\n",
    "                    s[j]=c\n",
    "        if '' in s : \n",
    "            return \"\"\n",
    "        \n",
    "        ##  验证构造是否合理\n",
    "        for i in range(n-1,-1,-1):\n",
    "            for j in range(n-1,-1,-1):\n",
    "                if s[i]== s[j]:\n",
    "                    if i == n-1 or j == n-1:\n",
    "                        if lcp[i][j]!=1:\n",
    "                            return \"\"\n",
    "                    elif lcp[i][j]!=lcp[i+1][j+1]+1:\n",
    "                        return \"\"\n",
    "                elif lcp[i][j]:\n",
    "                    return \"\"\n",
    "        return \"\".join(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheString(self, lcp: List[List[int]]) -> str:\n",
    "        n = len(lcp)\n",
    "        s = ['' for _ in range(n)]\n",
    "        i = 0\n",
    "        for c in range(26):\n",
    "            ch = chr(c+97)\n",
    "            while i<n and s[i]!='':\n",
    "                i+=1\n",
    "            if i==n:\n",
    "                break\n",
    "            for j in range(i,n):\n",
    "                if lcp[i][j] > 0:\n",
    "                    s[j] = ch\n",
    "        # print(s)\n",
    "        if \"\" in s:\n",
    "            return \"\"\n",
    "        # print(\"\".join(s))\n",
    "\n",
    "        for i in range(n-1,-1,-1):\n",
    "            for j in range(n-1,-1,-1):\n",
    "                if s[i] == s[j]:\n",
    "                    if i == n-1 or j == n-1:\n",
    "                        if lcp[i][j]!=1:\n",
    "                            return \"\"\n",
    "                    else:\n",
    "                        if lcp[i][j]!=lcp[i+1][j+1]+1:\n",
    "                            return \"\"\n",
    "                else:\n",
    "                    if lcp[i][j]!=0:\n",
    "                        return \"\"\n",
    "        return \"\".join(s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from string import ascii_lowercase as al\n",
    "class Solution:\n",
    "    def findTheString(self, lcp: List[List[int]]) -> str:\n",
    "        ls = len(lcp)\n",
    "        # 合规性检测\n",
    "        for i in range(ls):\n",
    "            if lcp[i][i] != ls - i:\n",
    "                return ''\n",
    "            for j in range(i, ls):\n",
    "                if lcp[i][j] != lcp[j][i] or lcp[i][j] + j > ls:\n",
    "                    return ''\n",
    "\n",
    "        s = [set(al) if i else 'a' for i in range(ls)]\n",
    "        # rule = r[i] = [j, k]\n",
    "        # s[i]必须与s[j]和s[k]一致\n",
    "        r = [set() for _ in range(ls)]\n",
    "\n",
    "        # 当前循环确定字符s[j]\n",
    "        for j in range(1, ls):\n",
    "            # 之前已经确定过字符s[j]了\n",
    "            if type(s[j]) == str:\n",
    "                continue\n",
    "            memo = s[j]\n",
    "            for i in range(j):\n",
    "                n = lcp[i][j]\n",
    "                # s[j]与s[i]的前n个字符一致\n",
    "                if n:\n",
    "                    # i < j，所以s[:j]已经在之前的循环中确定了\n",
    "                    for k in range(n):\n",
    "                        if s[i+k] not in s[j+k]:\n",
    "                            return ''\n",
    "                        s[j+k] = s[i+k]\n",
    "                    break\n",
    "                # s[j] != s[i]\n",
    "                else:\n",
    "                    if s[i] in s[j]:\n",
    "                        memo.remove(s[i])\n",
    "            if type(s[j]) == str:\n",
    "                pass\n",
    "            else:\n",
    "                if not memo:\n",
    "                    return ''\n",
    "                s[j] = min(memo)\n",
    "        \n",
    "        # 在确定了所有字符之后，重新检测一遍lcp表是否有误\n",
    "        for i in range(ls):\n",
    "            for j in range(i+1, ls):\n",
    "                n = lcp[i][j]\n",
    "                if s[i:i+n] != s[j:j+n]:\n",
    "                    return ''\n",
    "                if lcp[i][j] + j < ls and s[i:i+n+1] == s[j:j+n+1]:\n",
    "                    return ''\n",
    "\n",
    "        return ''.join(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheString(self, lcp: List[List[int]]) -> str:\n",
    "        # 对角线上：m,m-1,m-2...,1\n",
    "        # 对称\n",
    "        i=0\n",
    "        n=len(lcp)\n",
    "        s=['']*n\n",
    "        for q in range(26):\n",
    "            c=chr(ord('a')+q)\n",
    "            while i<n and s[i]!='':\n",
    "                i+=1\n",
    "            if i==n:\n",
    "                break\n",
    "            for j in range(i,n):\n",
    "                if lcp[i][j]!=0:\n",
    "                    s[j]=c\n",
    "        if '' in s:\n",
    "            return ''\n",
    "        \n",
    "        for i in range(n-1,-1,-1):\n",
    "            for j in range(n-1,-1,-1):\n",
    "                temp=0\n",
    "                if s[i]==s[j]:\n",
    "                    if i==n-1 or j==n-1:\n",
    "                        temp=1\n",
    "                    else:\n",
    "                        temp=lcp[i+1][j+1]+1\n",
    "                if temp!=lcp[i][j]:\n",
    "                    return \"\"\n",
    "        return ''.join(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from string import ascii_lowercase\n",
    "\n",
    "class Solution:\n",
    "    def findTheString(self, lcp: List[List[int]]) -> str:\n",
    "        i, n = 0, len(lcp)\n",
    "        s = [''] * n\n",
    "        # 尝试填充字符串s的每个位置\n",
    "        for c in ascii_lowercase:\n",
    "            while i < n and s[i]: \n",
    "                i += 1\n",
    "            if i == n: \n",
    "                break  # 当字符串s已填满，结束循环\n",
    "            for j in range(i, n):\n",
    "                if lcp[i][j]:\n",
    "                    s[j] = c\n",
    "\n",
    "        # 检查字符串s是否完全填满\n",
    "        if '' in s: \n",
    "            return \"\"  # 若没有填满，返回空字符串\n",
    "\n",
    "        # 验证构造的字符串与lcp矩阵是否一致\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                actual_lcp = 0 if s[i] != s[j] else 1 if i == n - 1 or j == n - 1 else lcp[i + 1][j + 1] + 1\n",
    "                if lcp[i][j] != actual_lcp: \n",
    "                    return \"\"\n",
    "\n",
    "        # 返回最后构造的字符串\n",
    "        return \"\".join(s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UF:\n",
    "    def __init__(self, n: int):\n",
    "        self.n = n + 5\n",
    "        self.p = [i for i in range(self.n)]\n",
    "\n",
    "    def find(self, x):\n",
    "        if self.p[x] != x: self.p[x] = self.find(self.p[x])\n",
    "        return self.p[x]\n",
    "\n",
    "    def union(self, a, b):\n",
    "        x, y = self.find(a), self.find(b)\n",
    "        if x == y: return\n",
    "        self.p[max(x, y)] = self.p[min(x, y)]\n",
    "            \n",
    "class Solution:\n",
    "    def findTheString(self, lcp: List[List[int]]) -> str:\n",
    "        n = len(lcp)\n",
    "        uf, q, g = UF(n), deque(), [[] for _ in range(n)]\n",
    "        val, deg = [0] * n, [0] * n\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                if lcp[i][j]:\n",
    "                    uf.union(i, j)\n",
    "                else:\n",
    "                    x, y = (i, j) if i < j else (j, i)\n",
    "                    g[x].append(y)\n",
    "                    deg[y] += 1\n",
    "        for i in range(n):\n",
    "            if deg[i] == 0: q.append(i)\n",
    "        while q:\n",
    "            u = uf.find(q.popleft())\n",
    "            for v in g[u]:\n",
    "                val[v] = max(val[v], val[u] + 1)\n",
    "                deg[v] -= 1\n",
    "                if deg[v] == 0: q.append(v)\n",
    "        res = ''\n",
    "        for i in range(n):\n",
    "            i = uf.find(i)\n",
    "            if val[i] > 25: return ''\n",
    "            res += chr(97 + val[i])\n",
    "            \n",
    "        for i in range(n-1,-1,-1):\n",
    "            if lcp[i][i] != n - i: return ''\n",
    "            for j in range(n-1,-1,-1):\n",
    "                if res[i] == res[j]:\n",
    "                    if i == n - 1 or j == n - 1:\n",
    "                        if lcp[i][j] != 1: return ''\n",
    "                    elif lcp[i][j] != lcp[i+1][j+1] + 1: return ''\n",
    "                elif lcp[i][j] != 0: return ''\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheString(self, lcp: List[List[int]]) -> str:\n",
    "        n = len(lcp)\n",
    "        adj = [[] for _ in range(n)]\n",
    "        # Basic checks\n",
    "        for i in range(n):\n",
    "            if lcp[i][i] != n - i:\n",
    "                return \"\"\n",
    "            for j in range(i + 1, n):\n",
    "                if lcp[i][j] != lcp[j][i]:\n",
    "                    return \"\"\n",
    "                if lcp[i][j] != 0:\n",
    "                    if j + 1 < n and lcp[i+1][j+1] != lcp[i][j] - 1:\n",
    "                        return \"\"\n",
    "                    adj[i].append(j)\n",
    "        for i in range(n):\n",
    "            if lcp[i][-1] > 1:\n",
    "                return \"\"\n",
    "\n",
    "        visited = [False] * n\n",
    "        ans = [''] * n\n",
    "        def dfs(c, i):\n",
    "            ans[i] = c\n",
    "            for nxt in adj[i]:\n",
    "                if not visited[nxt]:\n",
    "                    visited[nxt] = True\n",
    "                    dfs(c, nxt)\n",
    "        \n",
    "        cur = ord('a') - 1\n",
    "        for i in range(n):\n",
    "            if visited[i]:\n",
    "                continue\n",
    "            if cur == ord('z'):\n",
    "                return \"\"\n",
    "            cur += 1\n",
    "            visited[i] = True\n",
    "            dfs(chr(cur), i)\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                if ans[i] == ans[j]:\n",
    "                    if lcp[i][j] == 0:\n",
    "                        return \"\"\n",
    "                else:\n",
    "                    if lcp[i][j] != 0:\n",
    "                        return \"\"\n",
    "\n",
    "        return \"\".join(ans)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheString(self, lcp: List[List[int]]) -> str:\n",
    "        from string import ascii_lowercase\n",
    "        N = len(lcp)\n",
    "        if lcp[0][0] != N: return \"\"\n",
    "        res = [None]*N\n",
    "        line1 = lcp[0]\n",
    "        line1bak = list(line1)\n",
    "        charOff = 1\n",
    "        for i, c in enumerate(lcp[0]):\n",
    "            if c == 0:\n",
    "                if charOff == 26: return \"\"\n",
    "                char = ascii_lowercase[charOff]\n",
    "                charOff += 1\n",
    "                res[i] = line1[i] = char\n",
    "                for j, jc in enumerate(lcp[i]):\n",
    "                    if jc:\n",
    "                        res[j] = line1[j] = char\n",
    "            elif type(c) is int:\n",
    "                res[i] = 'a'\n",
    "        lcp[0] = line1bak\n",
    "        lastRow =[0]*N\n",
    "        for r, row in enumerate(lcp):\n",
    "            for c, v in enumerate(row):\n",
    "                if r == c:\n",
    "                    if v != N - r: \n",
    "                        return \"\"\n",
    "                if c < r:\n",
    "                    if v != lcp[c][r]: \n",
    "                        return \"\"\n",
    "                elif lastRow[c-1]:\n",
    "                    if v != lastRow[c-1] - 1: \n",
    "                        return \"\"\n",
    "                elif v:\n",
    "                    left, right = r, c\n",
    "                    while right < N and res[left] == res[right]:\n",
    "                        v -= 1\n",
    "                        left += 1\n",
    "                        right += 1\n",
    "                    if v: return \"\"\n",
    "            lastRow = row\n",
    "        return ''.join(res)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheString(self, lcp: List[List[int]]) -> str:\n",
    "        i, n = 0, len(lcp)\n",
    "        s = [''] * n\n",
    "        for c in ascii_lowercase:\n",
    "            while i < n and s[i]: i += 1\n",
    "            if i == n: break  # 构造完毕\n",
    "            for j in range(i, n):\n",
    "                if lcp[i][j]:\n",
    "                    s[j] = c\n",
    "        if '' in s: return \"\"  # 没有构造完\n",
    "\n",
    "        # 直接在原数组上验证\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                actual_lcp = 0 if s[i] != s[j] else 1 if i == n - 1 or j == n - 1 else lcp[i + 1][j + 1] + 1\n",
    "                if lcp[i][j] != actual_lcp: return \"\"\n",
    "        return \"\".join(s)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheString(self, lcp: List[List[int]]) -> str:\n",
    "        i, n = 0, len(lcp)\n",
    "        s = [''] * n\n",
    "        for c in ascii_lowercase:\n",
    "            while i < n and s[i]: i += 1\n",
    "            if i == n: break  # 构造完毕\n",
    "            for j in range(i, n):\n",
    "                if lcp[i][j]:\n",
    "                    s[j] = c\n",
    "        if '' in s: return \"\"  # 没有构造完\n",
    "\n",
    "        # 直接在原数组上验证\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                actual_lcp = 0 if s[i] != s[j] else 1 if i == n - 1 or j == n - 1 else lcp[i + 1][j + 1] + 1\n",
    "                if lcp[i][j] != actual_lcp: return \"\"\n",
    "        return \"\".join(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheString(self, lcp: List[List[int]]) -> str:\n",
    "        n = len(lcp)\n",
    "        ma = [[0] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            ma[i][i] = 1\n",
    "\n",
    "        llcp = [[0] *(n+1) for _ in range(n+1)]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                llcp[i][j] = lcp[i][j]\n",
    "            \n",
    "        for i in range(n):\n",
    "            for j in range(i,n):\n",
    "                if llcp[i][j] != llcp[j][i]:\n",
    "                    return ''\n",
    "                if llcp[i][j] > n-j:\n",
    "                    return ''\n",
    "                if (i==j or llcp[i][j]) and llcp[i][j] != llcp[i+1][j+1]+1:\n",
    "                    return ''\n",
    "                if llcp[i][j]:\n",
    "                    ma[i][j] = 1\n",
    "                    ma[j][i] = 1\n",
    "\n",
    "\n",
    "        table = [0] * n\n",
    "        c = 'a' \n",
    "        for i in range(n):\n",
    "            if table[i] == 0:\n",
    "                if ord(c) > ord('z'):\n",
    "                    return ''\n",
    "                for j in range(n):\n",
    "                    if ma[i][j]:\n",
    "                        if not table[j]:\n",
    "                            table[j] = c\n",
    "                        else:\n",
    "                            return \"\" \n",
    "                c = chr(ord(c) + 1)\n",
    "\n",
    "        return ''.join(table)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheString(self, lcp: List[List[int]]) -> str:\n",
    "        n = len(lcp)\n",
    "\n",
    "        s = [''] * n\n",
    "\n",
    "        i = 0\n",
    "\n",
    "        while i <= 26:\n",
    "            j = 0\n",
    "            while j < n and s[j] != '':\n",
    "                j += 1\n",
    "\n",
    "            if j == n:\n",
    "                break\n",
    "\n",
    "            c = chr(ord('a') + i)\n",
    "            s[j] = c\n",
    "\n",
    "            for k in range(n):\n",
    "                if lcp[j][k] > 0 and j != k:\n",
    "                    s[k] = c\n",
    "\n",
    "            i += 1\n",
    "\n",
    "        if i == 27:\n",
    "            return ''\n",
    "\n",
    "        s = ''.join(s)\n",
    "\n",
    "        f = [[0] * n for _ in range(n)]\n",
    "\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                if s[i] == s[j]:\n",
    "                    f[i][j] = 1\n",
    "\n",
    "                    if i < n - 1 and j < n - 1:\n",
    "                        f[i][j] = f[i + 1][j + 1] + 1\n",
    "\n",
    "        if f == lcp:\n",
    "            return s\n",
    "\n",
    "        return ''\n",
    "        \n",
    "            \n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheString(self, lcp: List[List[int]]) -> str:\n",
    "        n = len(lcp)\n",
    "        s = [\"\"] * n\n",
    "        last = 0\n",
    "        for i in range(n):\n",
    "            if s[i] != \"\":\n",
    "                continue\n",
    "            s[i] = chr(ord(\"a\") + last)\n",
    "            last += 1\n",
    "            for j in range(i + 1, n):\n",
    "                if lcp[i][j]:\n",
    "                    if s[j] != \"\":\n",
    "                        return \"\"\n",
    "                    s[j] = s[i]\n",
    "            if last == 26:\n",
    "                break\n",
    "        if \"\" in s:\n",
    "            return \"\"\n",
    "        # print(s)\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "        # dp[n][n] = 0 \n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                if s[i] == s[j]:\n",
    "                    if i + 1 < n and j + 1 < n:\n",
    "                        dp[i][j] = dp[i + 1][j + 1]\n",
    "                    dp[i][j] += 1\n",
    "                if dp[i][j] != lcp[i][j]:   \n",
    "                    # print(i, j, dp[i][j], lcp[i][j])\n",
    "                    return \"\"\n",
    "        return \"\".join(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheString(self, lcp: List[List[int]]) -> str:\n",
    "        x = 0\n",
    "        n = len(lcp)\n",
    "        ans = [\"\"]*n\n",
    "        for i in range(n):\n",
    "            if not ans[i] and x >= 26:\n",
    "                return \"\"\n",
    "            if ans[i]:\n",
    "                continue\n",
    "            if not ans[i]:\n",
    "                w = chr(x+ord(\"a\"))\n",
    "                ans[i] = w\n",
    "                x += 1\n",
    "            s = ans[i]\n",
    "            for j in range(i+1, n):\n",
    "                if lcp[i][j]:\n",
    "                    ans[j] = w\n",
    "            print(ans)\n",
    "            \n",
    "        dp = [[0]*(n+1) for _ in range(n+1)]\n",
    "        \n",
    "        for i in range(n-1, -1, -1):\n",
    "            for j in range(n-1, -1, -1):\n",
    "                if ans[i] == ans[j]:\n",
    "                    dp[i][j] = dp[i+1][j+1]+1\n",
    "                if dp[i][j] != lcp[i][j]:\n",
    "                    return \"\"\n",
    "        return \"\".join(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheString(self, lcp: List[List[int]]) -> str:\n",
    "        n = len(lcp)\n",
    "\n",
    "        fa = [i for i in range(n)]\n",
    "\n",
    "        def find(i):\n",
    "            if fa[i] == i:\n",
    "                return i\n",
    "            else:\n",
    "                fa[i] = find(fa[i])\n",
    "                return fa[i]\n",
    "\n",
    "        def merge(i, j):\n",
    "            fa[find(i)] = find(j)\n",
    "\n",
    "        for i in range(n):\n",
    "            if lcp[i][i] != n - i:\n",
    "                return ''\n",
    "\n",
    "            for j in range(i + 1, n):\n",
    "                if lcp[i][j] > n - j:\n",
    "                    return ''\n",
    "\n",
    "                if lcp[i][j] != lcp[j][i]:\n",
    "                    return ''\n",
    "\n",
    "                if lcp[i][j] > 0:\n",
    "                    merge(i, j)\n",
    "\n",
    "        smin = {}\n",
    "\n",
    "        for i in range(n):\n",
    "            f = find(i)\n",
    "            smin[f] = min(smin.get(f, inf), i)\n",
    "\n",
    "        if len(smin) > 26:\n",
    "            return ''\n",
    "\n",
    "        mapping = {}\n",
    "        for i, (v, k) in enumerate(sorted([(v, k) for k, v in smin.items()])):\n",
    "            mapping[k] = chr(ord('a') + i)\n",
    "\n",
    "        ret = []\n",
    "\n",
    "        for i in range(n):\n",
    "            ret.append(mapping[find(i)])\n",
    "\n",
    "        ret = ''.join(ret)\n",
    "\n",
    "        f = [[0] * n for _ in range(n)]\n",
    "\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(n - 1, - 1, -1):\n",
    "                if ret[i] == ret[j]:\n",
    "                    f[i][j] = 1\n",
    "                    if i + 1 < n and j + 1 < n:\n",
    "                        f[i][j] += f[i + 1][j + 1]\n",
    "\n",
    "        if f == lcp:\n",
    "            return ret\n",
    "        return ''\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "        \n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
